package com.lims.algorithm.algset.tree;

/**
 * <描述:> 无parent指针的bstree
 *
 * @author lims
 * @date 2020-04-25 14:07
 */
public class BSTreeNonP<T extends Comparable<T>> {
    static class BSTNpNode<T extends Comparable<T>> {
        T key;
        BSTNpNode<T> left;
        BSTNpNode<T> right;

        public BSTNpNode(T key, BSTNpNode<T> left, BSTNpNode<T> right) {
            this.key = key;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 根结点
     */
    private BSTNpNode<T> bstNpRoot;

    /**
     * 先序遍历
     */
    public void preOrderRecur() {
        preOrderRecur(bstNpRoot);
    }

    private void preOrderRecur(BSTNpNode<T> bstNpNode) {
        if (bstNpNode == null) {
            return;
        }
        System.out.print(bstNpNode.key + " ");
        preOrderRecur(bstNpNode.left);
        preOrderRecur(bstNpNode.right);
    }

    /**
     * 中序遍历
     */
    public void inOrderRecur() {
        inOrderRecur(bstNpRoot);
    }

    private void inOrderRecur(BSTNpNode<T> bstNpNode) {
        if (bstNpNode == null) {
            return;
        }
        inOrderRecur(bstNpNode.left);
        System.out.print(bstNpNode.key + " ");
        inOrderRecur(bstNpNode.right);
    }

    /**
     * 后序遍历
     */
    public void postOrderRecur() {
        postOrderRecur(bstNpRoot);
    }

    private void postOrderRecur(BSTNpNode<T> bstNpNode) {
        if (bstNpNode == null) {
            return;
        }
        postOrderRecur(bstNpNode.left);
        postOrderRecur(bstNpNode.right);
        System.out.print(bstNpNode.key + " ");
    }

    /**
     * contains 递归
     */
    public boolean containsRecur(T key) {
        return containsRecur(key, bstNpRoot);
    }

    private boolean containsRecur(T key, BSTNpNode<T> bstNpNode) {
        if (bstNpNode == null) {
            return false;
        }

        if (key.compareTo(bstNpNode.key) == 0) {
            return true;
        } else if (key.compareTo(bstNpNode.key) < 0) {
            boolean leftFlag = containsRecur(key, bstNpNode.left);
            if (leftFlag) {
                return true;
            }
        } else {
            boolean rightFlag = containsRecur(key, bstNpNode.right);
            if (rightFlag) {
                return true;
            }
        }
        return false;
    }

    /**
     * contains 非递归
     */
    public boolean contains(T key) {
        BSTNpNode<T> current = bstNpRoot;
        while (current != null) {
            if (key.compareTo(current.key) == 0) {
                return true;
            } else if (key.compareTo(current.key) < 0) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return false;
    }

    /**
     * 搜索key 递归
     */
    public BSTNpNode<T> searchRecur(T key) {
        return searchRecur(key, bstNpRoot);
    }

    private BSTNpNode<T> searchRecur(T key, BSTNpNode<T> bstNpNode) {
        if (bstNpNode == null) {
            return null;
        }
        BSTNpNode<T> searchNode = null;
        if (key.compareTo(bstNpNode.key) == 0) {
            return bstNpNode;
        } else if (key.compareTo(bstNpNode.key) < 0) {
            searchNode = searchRecur(key, bstNpNode.left);
        } else {
            searchNode = searchRecur(key, bstNpNode.right);
        }
        return searchNode;
    }

    /**
     * 搜索key 非递归
     */
    public BSTNpNode<T> search(T key) {
        return search(key, bstNpRoot);
    }

    private BSTNpNode<T> search(T key, BSTNpNode<T> bstNpNode) {
        if (bstNpNode == null) {
            return null;
        }
        BSTNpNode<T> current = bstNpNode;
        while (current != null) {
            if (key.compareTo(current.key) == 0) {
                return current;
            } else if (key.compareTo(current.key) < 0) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return null;
    }

    /**
     * finMin
     */
    public BSTNpNode<T> findMin(BSTNpNode<T> bstNpNode) {
        BSTNpNode<T> current = bstNpNode;
        while (current.left != null) {
            current = current.left;
        }
        return current;
    }

    /**
     * findMax
     */
    public BSTNpNode<T> findMax(BSTNpNode<T> bstNpNode) {
        BSTNpNode<T> current = bstNpNode;
        while (current.right != null) {
            current = current.right;
        }
        return current;
    }

    /**
     * 前驱
     */


    /**
     * 后继
     */

    /**
     * 插入 递归
     */
    public void insertRecur(T key) {
        BSTNpNode insertNode = new BSTNpNode(key, null, null);
        bstNpRoot = insertRecur(bstNpRoot, insertNode);
    }

    private BSTNpNode<T> insertRecur(BSTNpNode<T> bstNpNode, BSTNpNode<T> insertNode) {
        if (bstNpNode == null) {
            return insertNode;
        }
        if (insertNode.key.compareTo(bstNpNode.key) < 0) {
            // 插入根的左子树
            bstNpNode.left = insertRecur(bstNpNode.left, insertNode);
        } else if (insertNode.key.compareTo(bstNpNode.key) > 0) {
            // 插入根的右子树
            bstNpNode.right = insertRecur(bstNpNode.right, insertNode);
        } else {
            System.out.println("二叉树已经存在要插入的key：" + insertNode.key);
        }
        return bstNpNode;
    }

    /**
     * 插入 非递归
     */
    public void insert(T key) {
        BSTNpNode insertNode = new BSTNpNode(key, null, null);
        insert(bstNpRoot, insertNode);
    }

    private void insert(BSTNpNode<T> bstNpNode, BSTNpNode<T> insertNode) {
        if (bstNpNode == null) {
            return;
        }
        BSTNpNode<T> current = bstNpNode;
        while (current != null) {
            int cmp = insertNode.key.compareTo(current.key);
            if (cmp < 0) {
                if (current.left == null) {
                    current.left = insertNode;
                    return;
                }
                current = current.left;
            } else if (cmp > 0) {
                if (current.right == null) {
                    current.right = insertNode;
                    return;
                }
                current = current.right;
            } else {
                System.out.println("已经存在要插入的key:" + insertNode.key);
                return;
            }
        }
    }

    /**
     * 删除 递归
     */
    public void remove(T key) {
        BSTNpNode<T> delNode = searchRecur(key);
        remove(delNode, bstNpRoot);
    }

    private BSTNpNode<T> remove(BSTNpNode<T> delNode, BSTNpNode<T> bstNpNode) {
        if (bstNpNode == null || delNode == null) {
            return null;
        }
        int cmp = delNode.key.compareTo(bstNpNode.key);
        if (cmp < 0) {
            bstNpNode.left = remove(delNode, bstNpNode.left);
        } else if (cmp > 0) {
            bstNpNode.right = remove(delNode, bstNpNode.right);
        } else {
            // 有左右子树时，取右子树最小的给删除结点，然后在右子树上删除最小的那个
            if (bstNpNode.left != null &&
                    bstNpNode.right != null) {
                BSTNpNode<T> minRightNode = findMin(bstNpNode.right);
                delNode.key = minRightNode.key;
                delNode.right = remove(minRightNode, bstNpNode.right);
            } else {
                bstNpNode = bstNpNode.left != null ?
                        bstNpNode.left : bstNpNode.right;
            }
        }
        return bstNpNode;
    }

    /**
     * 删除 非递归
     */

    /*******************************分割线 测试程序***********************************/

    public static void main(String[] args) {
        /**
         * *                      39
         * *                  /        \
         * *               24           64
         * *             /     \      /    \
         * *            23      30    53    70
         * *                  /  \    \      \
         * *                26   35    60    75
         * *                 \               /
         * *                 27             72
         */
        /*****************递归****************/

        BSTreeNonP<Integer> bsTreeNonP = new BSTreeNonP<>();
        bsTreeNonP.insertRecur(39);
        bsTreeNonP.insertRecur(24);
        bsTreeNonP.insertRecur(64);
        bsTreeNonP.insertRecur(23);
        bsTreeNonP.insertRecur(30);
        bsTreeNonP.insertRecur(53);
        bsTreeNonP.insertRecur(60);

        bsTreeNonP.insertRecur(26);
        bsTreeNonP.insertRecur(27);
        bsTreeNonP.insertRecur(35);
        bsTreeNonP.insertRecur(70);
        bsTreeNonP.insertRecur(75);
        bsTreeNonP.insertRecur(72);

        System.out.println("root结点：" + bsTreeNonP.bstNpRoot.key);

        System.out.println("先序遍历");
        bsTreeNonP.preOrderRecur();
        System.out.println();
        System.out.println("中序遍历");
        bsTreeNonP.inOrderRecur();
        System.out.println();
        System.out.println("后序遍历");
        bsTreeNonP.postOrderRecur();
        System.out.println();

        System.out.println("递归constains(24):" + bsTreeNonP.containsRecur(24));
        System.out.println("非递归constains(24):" + bsTreeNonP.contains(24));

        System.out.println("递归search-24：" + bsTreeNonP.searchRecur(24));
        BSTNpNode<Integer> searchNode;
        System.out.println("递归search-24：" +
                (searchNode = bsTreeNonP.searchRecur(24)) != null ? searchNode.key : null);
        System.out.println("递归search-39：" +
                (searchNode = bsTreeNonP.searchRecur(39)) != null ? searchNode.key : null);
        System.out.println("递归search-72：" +
                (searchNode = bsTreeNonP.searchRecur(72)) != null ? searchNode.key : null);

        System.out.println("删除39");
        bsTreeNonP.remove(39);
        System.out.println("删除后遍历");
        System.out.println("先序遍历");
        bsTreeNonP.preOrderRecur();
        System.out.println();
        System.out.println("中序遍历");
        bsTreeNonP.inOrderRecur();
        System.out.println();
        System.out.println("后序遍历");
        bsTreeNonP.postOrderRecur();
        System.out.println();
    }
}
